/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/shortest-unsorted-continuous-subarray
   @Language: C++
   @Datetime: 19-05-15 15:33
   */

// Method 1, Time O(nlogn), Time 50ms
class Solution {
public:
	/**
	 * @param nums: an array
	 * @return: the shortest subarray's length
	 */
	int findUnsortedSubarray(vector<int> &nums) {
		// Write your code here
		int l=0, r=nums.size()-1;
		vector<int> sorted(nums);
		sort(sorted.begin(),sorted.end());
		for(; l<=r && sorted[l]==nums[l]; ++l);
		for(; r>=l && sorted[r]==nums[r]; --r);
		return l<r?r-l+1:0;
	}
};


// Method 2, Time O(n), Time 50ms
class Solution {
public:
	/**
	 * @param nums: an array
	 * @return: the shortest subarray's length
	 */
	int findUnsortedSubarray(vector<int> &nums) {
		// Write your code here
		int l=0, r=0, lmax=INT_MIN, rmin=INT_MAX;
		for(int i=0, j=nums.size()-1; j>-1; ++i, --j){
			lmax=max(lmax,nums[i]);
			rmin=min(rmin,nums[j]);
			if(lmax>nums[i]) r=i;
			if(rmin<nums[j]) l=j;
		}
		return l<r?r-l+1:0;
	}
};
